package pro.softzhang.algo.lc500;

import pro.softzhang.algo.flag.difficulty.DRed;

import java.util.HashMap;
import java.util.Map;

/**
 *
 */
@DRed
public class LC560_SubarraySumEqualsK {
    public static void main(String[] args) {
        // [1,2],[1,2,-1,1],[-1,1,3],
        int[] nums = new int[]{1, 2, -1, 1, 3};
        int k = 3;
        System.out.println(new Solution().subarraySum(nums, k));
    }

    static class Solution {
        public int subarraySum(int[] nums, int k) {
            int sum = 0, count = 0;
            Map<Integer, Integer> preSum = new HashMap<>((int)(nums.length / 0.75 + 1));
            preSum.put(0, 1);
            for (int num : nums) {
                sum += num;
                count += preSum.getOrDefault(sum - k, 0);
                preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
            }
            return count;
        }
    }
}
